We investigate the statistical properties of cut sizes generated by heuristicalgorithms which solve approximately the graph bisection problem. On anensemble of sparse random graphs, we find empirically that the distribution ofthe cut sizes found by ``local'' algorithms becomes peaked as the number ofvertices in the graphs becomes large. Evidence is given that this distributiontends towards a Gaussian whose mean and variance scales linearly with thenumber of vertices of the graphs. Given the distribution of cut sizesassociated with each heuristic, we provide a ranking procedure which takes intoaccount both the quality of the solutions and the speed of the algorithms. Thisprocedure is demonstrated for a selection of local graph bisection heuristics.
展开▼
